﻿#pragma once

#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iostream>

using namespace std;

/*
* 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。
*/

//尝试用双指针的方法解决
//双指针法：在数组已经排过序的情况下，从两端的指针同时进行移动，以减少轮询次数
namespace Solution_3
{
	//快排，时间复杂度 O(NlogN)
	vector<vector<int>> threeSum(vector<int>& nums)
	{
		vector<vector<int>> results;

		sort(nums.begin(), nums.end());

		for (int i = 0; i < nums.size(); ++i)
		{
			if (nums[i] > 0)
				return results;

			if (i >= 1 && nums[i] == nums[i - 1])
				continue;

			int left = i + 1;
			int right = nums.size() - 1;

			while (right > left)
			{
				if (nums[i] + nums[left] + nums[right] > 0)
					--right;
				else if (nums[i] + nums[left] + nums[right] < 0)
					++left;
				else
				{
					results.emplace_back(vector<int>{nums[i], nums[left], nums[right] });
					while (right > left)
					{
						if (nums[right] == nums[right - 1])
							--right;
						else if (nums[left] == nums[left + 1])
							++left;
						else
							break;
					}
					//同时移动
					--right;
					++left;
				}
			}
		}

		return results;
	}

	void Answer()
	{
		vector<int> nums{
			-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6
		};

		auto result = threeSum(nums);

		for (auto& elem : result)
		{
			for (int num : elem)
			{
				cout << num << ", ";
			}
			cout << "\n";
		}
	}
}
